#include <iostream>

using namespace std;                  // Function prototypes

void Get_Data(int [], int);
void Display(int [], int);
void Do_S_Sort(int [], int);
int  Find_Least(const int [], int, int);
int  Compare(const int &, const int &);
void Swap(int &, int &);

int main() {
  const int max = 1000;
  int List[max];
  Get_Data(List, max);                 // Obtain data
  cout << "Initial list" << endl;
  Display(List, max);                  // Show it
  Do_S_Sort(List, max);                // Sort it
  cout << "Sorted list" << endl;
  Display(List, max);                  // Show it again
  return 0;
}

// Obtain data to sort from standard input
void Get_Data(int a[], int n) {
  cout << "Please enter " << n << " integers" << endl;
  for (int i = 0; i < n; ++i)
     cin >> a[i];
}

// Display the current contents of list
void Display(int a[], int n) {
  for(int i = 0; i < n; ++i)
     cout << " " << a[i];
  cout << endl;
}

// Do the Selection Sort, Display after each pass
void Do_S_Sort(int a[], int n) {
  int index;
  for (int i = 0; i < n-1; ++i) {
    index = Find_Least( a, i, n );
    if (i != index)
      Swap(a[i], a[index]);
    cout << "After pass " << i+1 << " : ";
    Display(a, n);
  }
}

// Find the index of the least element in list
int Find_Least(const int a[], int start, int stop) {
  int Index_of_Least = start;
  for (int i = start+1; i < stop; ++i )
    if (Compare(a[i], a[Index_of_Least]))
      Index_of_Least = i;
  return Index_of_Least;
}

// Compare two data elements
int Compare(const int &a, const int &b) {
  return (a < b);
}

// Exchange two data elements
void Swap(int &a, int &b) {
  int temp;
  temp = a;
  a = b;
  b = temp;
}
